class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ret;
        int max = n - 1;
        while (max > 1)
        {
            int left = 0;
            int right = max - 1;
            while (left < right)
            {
                int tmp = nums[left] + nums[right] + nums[max];
                if (tmp < 0)
                    left++;
                else if (tmp > 0)
                    right--;
                else
                {
                    ret.push_back({ nums[left],nums[right],nums[max] });
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1])
                        left++;
                    while (left < right && nums[right] == nums[right + 1])
                        right--;
                }

            }
            max--;
            while (max > 1 && nums[max] == nums[max + 1])
                max--;
        }
        return ret;
    }
};


class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int prev = 0;
        int cur = 0;
        int k = 0;
        while (cur < n)
        {
            if (nums[cur] != val)
            {
                nums[prev++] = nums[cur];
                k++;
            }
            cur++;
        }
        return k;
    }
};



class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n < 2)
            return n;
        int cur = 1;
        int prev = 0;
        int k = 1;
        while (cur < n)
        {
            if (nums[cur] != nums[cur - 1])
            {
                ++k;
                nums[++prev] = nums[cur];
            }
            cur++;
        }
        nums.resize(k);
        return k;
    }
};


class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n < 2)return n;
        int prev = 0;
        int cur = 1;
        int k = 1;

        while (cur < n)
        {
            if (nums[cur] == nums[cur - 1])
            {
                int flag = 1;
                while (cur < n && nums[cur] == nums[cur - 1])
                {
                    flag++;
                    if (flag <= 2)
                    {
                        nums[++prev] = nums[cur];
                        k++;
                    }
                    ++cur;
                }
            }
            else
            {
                nums[++prev] = nums[cur];
                cur++;
                k++;
            }
        }
        cout << k;
        return k;
    }
};


class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        if (n == 1)
            return nums[0];
        int cur = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (nums[i] == nums[j])
                {
                    if ((j - i + 1) > (n / 2))
                        return nums[i];
                    continue;
                }
                else
                    break;
            }
        }
        return 0;
    }
};

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        reverse(nums.begin(), nums.begin() + n - k);
        reverse(nums.begin() + n - k, nums.end());
        reverse(nums.begin(), nums.end());
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int leftmin = 0;
        int ret = 0;
        for (int i = 1; i < n; i++)
        {
            if (prices[i] > prices[leftmin])
                ret = max(ret, prices[i] - prices[leftmin]);
            else
                leftmin = i;
        }
        return ret;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> mr(n, 0);
        vector<int> mc(n, 0);
        mr[0] -= prices[0];
        for (int i = 1; i < n; i++)
        {
            mr[i] = max(mr[i - 1], mc[i - 1] - prices[i]);
            mc[i] = max(mr[i - 1] + prices[i], mc[i - 1]);
        }
        return mc[n - 1];
    }
};

class Solution {
public:
    int end;
    bool dfs(vector<int>& nums, int pos)
    {
        if (pos == end)return true;
        if (nums[pos] == 0)return false;
        for (int i = 1; i < nums[pos]; i++)
        {
            cout << "k- ";
            if (pos + i >= end)return true;
            if (dfs(nums, pos + i))
                return true;
        }
        return false;
    }
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        end = n - 1;
        return dfs(nums, 0);
    }
};

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int right = nums[0];

        int left = 0;
        for (int i = left; i <= right && right < n; i++)
        {
            right = max(right, nums[i] + i);
            cout << right << " ";
        }

        if (right >= n - 1)
            return true;
        return false;
    }
};

